"""
@author: Lin
@time: 2022/7/24 9:11
排序练习
"""
from utils.array_utils import sjlb, check_all, swap


def bubble(arr):
    for index in range(len(arr)):
        for j in range(len(arr) - 1):
            if arr[j] > arr[j + 1]:
                # print(f'swap {j}, {j + 1}')
                swap(arr, j, j + 1)
            # print(arr)


def insert(arr):
    for i in range(len(arr)):
        cur = arr[i]
        while i > 0 and cur < arr[i - 1]:
            arr[i] = arr[i - 1]
            i -= 1
        arr[i] = cur


def insert_02(arr):
    for i in range(1, len(arr)):
        t = arr[i]
        while i > 0 and t < arr[i - 1]:
            arr[i] = arr[i - 1]
            i -= 1
        arr[i] = t


def shell(arr):
    n = 2
    step = len(arr) // n
    while step > 0:
        # print('step:', step)
        for i in range(step, len(arr), step):
            # print(arr[i])
            cur = arr[i]
            while i > 0 and cur < arr[i - step]:
                arr[i] = arr[i - step]
                i -= step
            arr[i] = cur
        step //= n


def shell_02(arr):
    n = 2
    step = len(arr) // n
    while step > 0:
        # print(step)
        for i in range(step, len(arr), step):
            t = arr[i]
            while i > 0 and t < arr[i - step]:
                arr[i] = arr[i - step]
                i -= step
            arr[i] = t
        step //= n


def merge(la, lb):
    ia = ib = 0
    lc = []
    while ia < len(la) and ib < len(lb):
        if la[ia] < lb[ib]:
            lc.append(la[ia])
            ia += 1
        else:
            lc.append(lb[ib])
            ib += 1
    lc += la[ia:]
    lc += lb[ib:]
    return lc


def merge_sort(arr):
    if len(arr) == 1:
        return arr
    mid = len(arr) // 2
    arr_left = arr[:mid]
    arr_right = arr[mid:]
    return merge(merge_sort(arr_left), merge_sort(arr_right))


def partition(arr, r, l=None):
    if l is None:
        l = len(arr)
    t = arr[r]
    s = r - 1  # 小于区右边界
    b = l  # 大于区左边界
    cur = r
    while cur < b:
        if cur < t:
            swap(arr, cur, s + 1)
            s += 1
            cur += 1
        elif cur > t:
            swap(arr, cur, b - 1)
            b -= 1
        else:
            cur += 1
    return s, b


def swap(arr, a, b):
    arr[a], arr[b] = arr[b], arr[b]


def zhishu(n):
    if n < 2:
        return False
    for i in range(2, n):
        if n % i == 0:
            return False
    return True


if __name__ == '__main__':
    ll = sjlb()
    ll = [6, 4, 9, 1, 0, 5, 3, 8]
    # insert(ll)
    # insert_02(ll)
    # shell(ll)
    shell_02(ll)
    print(partition(ll, 0))
    # print('merge_sort: ', merge_sort(ll))
    print(ll)
    # print(check_all(bubble, 1000))
    # print(check_all(insert_02, 1000))
    # print(check_all(shell, 1000))
    # print(check_all(shell_02, 1000))
    # print(check_all(merge_sort, 1000))
    for i in range(100):
        if zhishu(i):
            print(i, end=' ')
